In the past years, Interconnection Networks have been used quite often andespecially in applications where parallelization is critical. Message packetstransmitted through such networks can be interrupted using buffers in order tomaximize network usage and minimize the time required for all messages to reachtheir destination. However, preempting a packet will result in topologyreconfiguration and consequently in time cost. The problem of schedulingmessage packets through such a network is referred to as PBS and is known to beNP-Hard. In this paper we have improved, critically, variations of polynomiallysolvable instances of Open Shop to approximate PBS. We have combined thesevariations and called the induced algorithm IHSA, Improved Hybridic SchedulingAlgorithm. We ran experiments to establish the efficiency of IHSA and foundthat in all datasets used it produces schedules very close to the optimal. Inaddition, we tested IHSA with datasets that follow non-uniform distributionsand provided statistical data which illustrates better its performance.Tofurther establish the efficiency of IHSA we ran tests to compare it to SGA,another algorithm which when tested in the past has yielded excellent results.
展开▼
